/*
 * @Author: liusheng
 * @Date: 2022-04-26 16:42:47
 * @LastEditors: liusheng
 * @LastEditTime: 2022-04-26 17:15:23
 * @Description: 剑指 Offer II 044. 二叉树每层的最大值
 * email:liusheng613@126.com
 * Copyright (c) 2022 by liusheng/liusheng, All Rights Reserved. 
 * 
 * 剑指 Offer II 044. 二叉树每层的最大值
给定一棵二叉树的根节点 root ，请找出该二叉树中每一层的最大值。

 

示例1：

输入: root = [1,3,2,5,3,null,9]
输出: [1,3,9]
解释:
          1
         / \
        3   2
       / \   \  
      5   3   9 
示例2：

输入: root = [1,2,3]
输出: [1,3]
解释:
          1
         / \
        2   3
示例3：

输入: root = [1]
输出: [1]
示例4：

输入: root = [1,null,2]
输出: [1,2]
解释:      
           1 
            \
             2     
示例5：

输入: root = []
输出: []
 

提示：

二叉树的节点个数的范围是 [0,104]
-231 <= Node.val <= 231 - 1
 

注意：本题与主站 515 题相同： https://leetcode-cn.com/problems/find-largest-value-in-each-tree-row/
 */

#include "header.h"
// Definition for a binary tree node.
struct TreeNode {
    int val;
      TreeNode *left;
      TreeNode *right;
      TreeNode() : val(0), left(nullptr), right(nullptr) {}
      TreeNode(int x) : val(x), left(nullptr), right(nullptr) {}
      TreeNode(int x, TreeNode *left, TreeNode *right) : val(x), left(left), right(right) {}
};

/*
solution use queue
traverse by level,the current level node's nums is the current queue's size
*/
class Solution {
public:
    vector<int> largestValues(TreeNode* root) {
        if (!root)
        {
            return {};
        }
        queue<TreeNode *> levelQ;
        levelQ.push(root);
        
        vector<int> levelMaxs;
        while (!levelQ.empty())
        {
            int curLevelNodesNum = levelQ.size();
            int curLevelMax = INT_MIN;
            for (int i = 0; i < curLevelNodesNum; ++i)
            {
                TreeNode * curNode = levelQ.front();
                levelQ.pop();
                
                //record the max node val in current level
                if (curLevelMax < curNode->val)
                {
                    curLevelMax = curNode->val;
                }
                
                if (curNode->left)
                {
                    levelQ.push(curNode->left);
                }
                
                if (curNode->right)
                {
                    levelQ.push(curNode->right);
                }
            }
            levelMaxs.push_back(curLevelMax);
        }
        
        return levelMaxs;
    }
};

/*
solution use recursion:
use unorder_map to record every level's max value
*/
class Solution2 {
public:
    vector<int> largestValues(TreeNode* root) {
        findMaxRecursive(root,0);
        int levelNum = levelMaxMap.size();
        vector<int> levelMaxVals(levelNum);
        for (int i = 0; i < levelNum; ++i)
        {
            levelMaxVals[i] = levelMaxMap[i];
        }

        return levelMaxVals;
    }
private:
    void findMaxRecursive(TreeNode * root,int level)
    {
        if (!root)
        {
            return;
        }

        if (levelMaxMap.count(level))
        {
            levelMaxMap[level] = max(levelMaxMap[level],root->val);
        }
        else
        {
            levelMaxMap[level] = root->val;
        }

        //find the next level recursively
        findMaxRecursive(root->left,level + 1);
        findMaxRecursive(root->right,level + 1);
    }
private:
    unordered_map<int,int> levelMaxMap;
};